package com.wangjie.stackandqueue;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author jieshao
 * @date 2022/5/13 15:46
 *
 * 503. 下一个更大元素 II
 */
public class Test09 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 1};
        int[] res = nextGreaterElements(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 模拟数组的长度翻倍
        for (int i = 2 * n - 1; i >= 0; i--) {
            while (!s.empty() && s.peek() <= nums[i % n]) {
                s.pop();
            }
            res[i % n] = s.empty() ? -1 : s.peek();
            s.push(nums[i % n]);
        }
        return res;
    }
}